package com.xx.springboot.DataStructure.LinkedList;

/**
 * Created by xiaoxiunique on 2018-7-23.
 */
public class LinkedList<E> {
    private class Node{
        private E e;
        private Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    // 链表长度
    private int size;

    // 链表头结点
    private Node dummyNode;

    public LinkedList() {
        dummyNode = new Node(null, null);
        size = 0;
    }

    /**
     * 获取得到链表长度
     * @return
     */
    public int getSize() {

        return size;
    }

    /**
     * 判断链表是否为空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在指定索引位置添加元素
     * @param index
     * @param e
     */
    public void add(int index, E e) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index error");
        }

        Node cur = dummyNode;
        for (int i = 0 ; i < index; i++) {
            cur = cur.next;
        }

        Node node = new Node(e);
        node.next = cur.next;
        cur.next = node;
        size++;
    }

    /**
     * 在头结点处 添加元素
     * @param e
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 在链表的末尾添加元素
     * @param e
     */
    public void addLast(E e) {
        add(size, e);
    }

    /**
     * 更新指定位置的元素
     * @param index
     * @param e
     * @return
     */
    public void update(int index, E e) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index error");
        }

        Node cur = dummyNode.next;
        for (int i = 0 ; i < index ; i ++) {
            cur = cur.next;
        }
        cur.e = e;
    }


    /**
     * 删除指定位置的元素
     * @param index
     * @return
     */
    public E remove(int index) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index error");
        }

        Node prev = dummyNode;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        Node cur = prev.next;
        prev.next = cur.next;
        cur.next = null;
        size --;
        return cur.e;
    }

    /**
     * 删除头节点
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 删除链表的最后一个节点
     * @return
     */
    public E removeLast() {
        return remove(size - 1);
    }

    /**
     * 删除链表中的指定元素
     * @param e
     */
    public void removeElement(E e) {

        Node prev = dummyNode;
        while (prev.next != null) {
            if (e.equals(prev.e))
                break;
            prev = prev.next;
        }

        if (prev.next != null) {
            Node cur = prev.next;
            prev.next = cur.next;
            cur.next = null;
            size --;
        }
    }



    /**
     * 判断链表中是否有元素e
     * @param e
     * @return
     */
    public boolean contains(E e) {
        Node cur = dummyNode.next;

        while (cur != null) {
            if (e.equals(cur.e)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 获取 索引为 index 位置的元素
     * @param index
     * @return
     */
    public E get(int index) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("数组越界");
        }
        Node cur = dummyNode.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.e;
    }

    /**
     * 获取得到链表的最后一个元素
     * @return
     */
    public E getLast() {
        return get(size - 1);
    }

    /**
     * 获取得到链表的第一个元素
     * @return
     */
    public E getFirst() {
        return get(0);
    }

    @Override
    public String toString() {
        StringBuffer res = new StringBuffer();
        Node cur = dummyNode.next;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(0, 0);
        list.add(1, 1);
        list.add(2, 2);
        list.add(3, 3);
        list.add(4, 4);
        list.add(5, 5);
        list.add(6, 6);
        //list.remove(0);;


        System.out.println(list);
        System.out.println(list.get(3));
    }
}
